4.3 AVL树
AVL 树 是 二叉搜索树 的一个自平衡扩展，它通过旋转操作来保持树的平衡。
与普通的二叉搜索树不同，AVL 树在每次插入或删除节点时，都会检查树的平衡因子，并进行必要的调整以确保树的高度尽可能保持平衡。
本节我们将介绍AVL 树的基本概念、平衡因子、旋转操作，以及AVL 树的Go语言实现。
本节代码存放目录为 lesson8
概念及原理
AVL 树 是第一种被发明的自平衡二叉搜索树，由两位苏联科学家Adelson-Velsky和Landis在1962年提出，因此得名AVL 树。
AVL 树的特点如下：
AVL 树是二叉搜索树，所以它具有二叉搜索树的所有基本特性（左子小于父，右子大于父）。它保持了自平衡，即对于每个节点，左子树和右子树的高度差不能超过
1，这个高度差被称为平衡因子。通过旋转操作来保持树的平衡，当插入或删除节点时，如果发现树失衡，就通过左旋或右旋来恢复平衡。
平衡因子： 节点左子树的高度减去右子树的高度。
根据平衡因子的不同，可以判断节点是否失衡。
平衡因子 = -1, 0, 1，表示节点是平衡的。平衡因子 > 1 或 < -1，表示节点失衡，需要进行旋转操作来恢复平衡。
平衡因子 = 左子树高度 - 右子树高度
总的来说就是：当左右子树的高度差异超过1时，那么树就不平衡，就需要进行旋转操作来让树保持平衡。
如下图所示为平衡的二叉树：
8
/ \
4 10
/ \ \
2 6 12
在上面的示意中：
节点 8 的平衡因子=左子树高度(2)-右子树高度(2)=0，是平衡的。节点 4 的平衡因子=左子树高度(1)-右子树高度(1)=0，是平衡的。节点 10 的平衡因子=左子树高度(0)-右子树高度(1)=-1，是平衡的。
上面的每一个父节点平衡左右子树的高度差都没有超过1，所以整个二叉树都是平衡的。
如下图所示为失衡的二叉树：
8
/ \
4 10
/ \ \
2 6 12
\
14
在上面的示意中，节点 10 的平衡因子 = 左子树高度(0) - 右子树高度(2) = -2。
最终平衡因子超过了规则设定的1，所以这个二叉树是不平衡的，需要进行旋转操作。
旋转后结果如下：
8
/ \
4 12
/ \ / \
2 6 10 14
总的来说，其实旋转操作就是将原本不平衡的二叉树进行一个重新排列，最终形成平衡的二叉树。
旋转操作
在AVL 树中，当节点失衡时，通过旋转来恢复树的平衡。常见的旋转有四种：
左旋：当右子比左子高，进行左旋。
右旋：当左子比右子高，进行右旋。
左右旋：当左子的右子导致失衡时，先对左子进行左旋，然后对当前节点进行右旋。
右左旋：当右子树的左子树导致失衡时，先对右子树进行右旋，然后对当前节点进行左旋。
左旋示意图
1. 初始状态：
10
\
20
\
30
2. 左旋过程：
20
/ \
10 30
初始状态：
10的右子树高度过高，平衡因子为-2。左旋步骤：右子比左子高，需要左旋。我们围绕
10节点左旋，使20成为新的根节点，10变成20的左子节点，30保持为20的右子节点。
右旋示意图
1. 初始状态：
30
/
20
/
10
2. 右旋过程：
20
/ \
10 30
初始状态：
30的左子树高度过高，平衡因子为2。右旋步骤：左子比右子高，需要右旋。我们围绕
30节点右旋，使20成为新的根节点，30变成20的右子节点，10保持为20的左子节点。
左右旋
1. 初始状态：
30
/
10
\
20
2. 第一步左旋（围绕 10）：
30
/
20
/
10
3. 第二步右旋（围绕 30）：
20
/ \
10 30
初始状态：
30的左子树失衡，由于10还有右子树，所以需要经过两步操作。左右旋步骤：左子
10的右子20导致失衡，进行左右旋。第一步左旋：围绕
10进行左旋，使20成为10的父节点。第二步右旋：围绕
30进行右旋，使20成为新的根节点。
右左旋
1. 初始状态：
10
\
30
/
20
2. 第一步右旋（围绕 30）：
10
\
20
\
30
3. 第二步左旋（围绕 10）：
20
/ \
10 30
初始状态：
10的右子树失衡，由于30还有左子树，所以需要经过两步操作。右左旋步骤：右子的左子导致失衡，进行右左旋。
第一步右旋：围绕
30进行右旋，使20成为30的父节点。第二步左旋：围绕
10进行左旋，使20成为新的根节点。
AVL 树的插入操作
在AVL 树中，插入节点的步骤如下：
首先，按照二叉搜索树的规则插入新节点。
然后，从插入点向上回溯，检查每个祖先节点的平衡因子。
如果某个节点的平衡因子超过了范围
（-1, 0, 1），则需要通过旋转操作来恢复平衡。
AVL 树的删除操作与二叉搜索树类似，但需要在删除后检查是否打破了树的平衡，并通过旋转操作来恢复平衡。
Go语言的实现
实现代码如下所示：
// Tree 定义树结构
type Tree struct {
data int
left *Tree
right *Tree
height int
}
// 获取节点的高度
func (t *Tree) getHeight() int {
if t == nil {
return 0
}
return t.height
}
// 计算平衡因子
func (t *Tree) getBalanceFactor() int {
if t == nil {
return 0
}
return t.left.getHeight() - t.right.getHeight()
}
// 更新节点的高度
func (t *Tree) updateHeight() {
leftHeight := t.left.getHeight()
rightHeight := t.right.getHeight()
if leftHeight > rightHeight {
t.height = leftHeight + 1
} else {
t.height = rightHeight + 1
}
}
// 左旋操作
func (t *Tree) leftRotate() *Tree {
newRoot := t.right
t.right = newRoot.left
newRoot.left = t
// 更新高度
t.updateHeight()
newRoot.updateHeight()
return newRoot
}
// 右旋操作
func (t *Tree) rightRotate() *Tree {
newRoot := t.left
t.left = newRoot.right
newRoot.right = t
// 更新高度
t.updateHeight()
newRoot.updateHeight()
return newRoot
}
// 插入节点
func (t *Tree) insert(data int) *Tree {
if t == nil {
return &Tree{data: data, height: 1}
}
if data < t.data {
t.left = t.left.insert(data)
} else if data > t.data {
t.right = t.right.insert(data)
} else {
// 不允许重复节点
return t
}
// 更新当前节点的高度
t.updateHeight()
// 检查是否需要旋转
balance := t.getBalanceFactor()
// 左子树过高，进行右旋
if balance > 1 {
if data < t.left.data {
return t.rightRotate()
}
// 左右情况，先左旋后右旋
if data > t.left.data {
t.left = t.left.leftRotate()
return t.rightRotate()
}
}
// 右子树过高，进行左旋
if balance < -1 {
if data > t.right.data {
return t.leftRotate()
}
// 右左情况，先右旋后左旋
if data < t.right.data {
t.right = t.right.rightRotate()
return t.leftRotate()
}
}
return t
}
// 中序遍历
func (t *Tree) inOrder() {
if t == nil {
return
}
t.left.inOrder()
fmt.Printf("%d ", t.data)
t.right.inOrder()
}
func main() {
root := &Tree{data: 10}
root = root.insert(20)
root = root.insert(30)
root = root.insert(40)
root = root.insert(50)
root = root.insert(25)
fmt.Println("中序遍历结果：")
root.inOrder() // 输出：10 20 25 30 40 50
}
执行结果输出如下所示：
中序遍历结果：
10 20 25 30 40 50
小结
AVL 树是一种自平衡的二叉搜索树，通过旋转操作来保持树的平衡，从而提高查找、插入和删除操作的效率。
通过本节的学习，我们了解了AVL树的特性、旋转操作以及如何使用Go语言实现AVL 树。
下一节我们将继续学习红黑树，它也是一种自平衡二叉搜索树，并且广泛应用于各种编程语言的标准库中。